#include <iostream>
#include <vector>
#include"BinarySearchTree.h"
#include<algorithm>
#include<cstdio>
#include<ctime>
#include"random.h"
using namespace std;

template <typename Comparable>
void  BSTSorting(std::vector<Comparable> &_arr, int _mode = 1)
{
	BinarySearchTree<Comparable> t;
	if (_mode =1)
	{
		srand((unsigned int)time(0));
		random_shuffle(_arr.begin(), _arr.end());
	}
    for (vector<int>::iterator it = _arr.begin();
		it != _arr.end();
		it++)
		{
			t.insert(*it);
		}
	t.printTree();
};  



/**
 * @brief 主程序flag的数字来操控进行最坏效率还是平均效率，flag为0对应平均效率，flag为1对应最坏效率；
 * num为排序向量的长度；mode的作用如作业要求相同。输入两个数，第一个为mode，第二个为flag。
 * 
 * @return int 
 */

int main()
{
	create_rand obj;

	int mode;
	cin >> mode;
	int num = 10000;
	int flag = 0;
	cin >> flag;
	std::vector<int> input(num);
		
	if (flag ==0)
	{input = obj.create_rand_int_number_include_a(0, 1000000, num);}
	else if (flag==1)
	{
	for (int i = 0; i < num; ++i)
		{
		input[i] = i;
		}
	}
	/**
	 * @brief else里面为异常处理，当flag的值不为0或1
	 *则显示输出错误，并且终止程序。
	 * 
	 */
	else 
	{
		try 
		{
			throw UnderflowException();
		}
		catch(UnderflowException& e)
		{
			cout <<"输入错误" << endl;
			exit(2);
		}		
	}
	
	clock_t startTime =clock();
	BSTSorting(input,mode);
	clock_t endTime = clock();
    cout << "sorting time :" << double(endTime - startTime)/ CLOCKS_PER_SEC << "s" << endl;
	return 0;
}
